package memory;


import java.util.Arrays;

public class Exercises2 {
    // 62、不同路径

    public int uniquePaths2(int m, int n) {
        // 动态规划
        int[][] dp = new int[m + 1][n + 1];
        dp[1][1] = 1;
        for(int i = 1;i <= m;i++) {
            for(int j = 1;j <= n;j++) {
                if (i == 1 && j == 1) {
                    continue;
                }
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m][n];
    }

    //记忆化搜索
    public int uniquePaths(int m, int n) {
        int[][] memo = new int[m + 1][n + 1];
        return dfs(m,n,memo);
    }

    public int dfs(int i,int j,int[][] memo) {
        if(memo[i][j] != 0) {
            return memo[i][j];
        }

        if(i == 0 || j == 0) {
            return 0;
        }

        if(i == 1 && j == 1) {
            memo[i][j] = 1;
            return 1;
        }

        memo[i][j] = dfs(i - 1,j,memo) + dfs(i,j - 1,memo);

        return memo[i][j];
    }
}
